// 快速幂、Miller-Rabin
// https://soj.turingedu.cn/problem/50500/   超时

ll quick_mul(ll a, ll b, ll mod) { // 防溢乘法取模
    ll back = 0;
    for (; b > 0; a = (a << 1) % mod, b >>= 1)
        if (b & 1) back = (back + a) % mod;
    return back;
}

ll quick_pow(ll a, ll b, ll mod) { // 快速幂取模
    ll back = 1;
    for (a %= mod; b > 0; a = quick_mul(a, a, mod), b >>= 1)
        if (b & 1) back = quick_mul(back, a, mod);
    return back;
}

bool millerRabin(ll n) { // 素数概率性测试
    if (n <= 3) return n > 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    ll t = n - 1, k = 0; // n - 1 = t * (2 ^ k)
    while (t % 2 == 0)
        t /= 2, ++k;
    for (int i = 1, ed = 10; i <= ed; ++i) {
        ll a = ((ll)rand() * rand()) % (n - 2) + 2; // [2, n - 1]
        ll base = quick_pow(a, t, n), last;         // a ^ t
        for (int j = 0; j < k; ++j) {
            last = base;
            base = quick_mul(base, base, n);
            if (base == 1 && last != 1 && last != n - 1) return 0; // 二次平方探测定理
        }
        if (base != 1) return 0; // 费马小定理
    }
    return 1;
}
